package com.leetcode.array;

/**
 *乘积最大子数组
 * 给你一个整数数组 nums，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
 * 示例 1:
 * 输入: [2,3,-2,4]
 * 输出: 6
 * 解释:子数组 [2,3] 有最大乘积 6。
 * 示例 2:
 * 输入: [-2,0,-1]
 * 输出: 0
 * 解释:结果不能为 2, 因为 [-2,-1] 不是子数组。
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xmk3rv/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * @author ymy
 * @date 2021年08月31日 14:35
 */
class Code152 {
    public static void main(String[] args) {
        int[] nums = {2,3,-2,4};
        int i = maxProduct(nums);
        System.out.println(i);
    }
    /**
     * 动态规划转移方程
     * fmax(i)=max{f(i−1)*nums[i],nums[i]}
     * fmin(i)=max{f(i−1)*nums[i],nums[i]}
     */
    public static int maxProduct(int[] nums) {
        int maxPer = nums[0];
        int minPer = nums[0];
        int maxNum = nums[0];
        for(int i=1;i<nums.length;i++){
            int mxp = maxPer;
            int mnp = minPer;
            maxPer = Math.max(mxp * nums[i],Math.max(mnp*nums[i],nums[i]));
            minPer = Math.min(mxp * nums[i],Math.min(mnp*nums[i],nums[i]));
            maxNum = Math.max(maxPer,maxNum);
        }
        return maxNum;
    }
}
